<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Cyclic types
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora207.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora209.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Cyclic types</H2>
<A NAME="@concepts362"></A>
<A NAME="@fonctions492"></A>In Objective CAML, it is possible to declare recursive data structures: such a
structure may contain a value with precisely the same structure.<BR>
<BR>


<PRE>
<CODE> </CODE><BR># <B>type</B><CODE> </CODE>sum_ex1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Ctor<CODE> </CODE><B>of</B><CODE> </CODE>sum_ex1<CODE> </CODE>;;<BR><CODE>type sum_ex1 = | Ctor of sum_ex1</CODE><BR><BR># <B>type</B><CODE> </CODE>record_ex1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>field<CODE> </CODE><CODE>:</CODE><CODE> </CODE>record_ex1<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type record_ex1 = { field: record_ex1 }</CODE><BR>

</PRE>
<BR>
<BR>
How to build values with such types is not obvious, since we need a value
before building one! The recursive declaration of values allows to get out of
this vicious circle.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>sum_val<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Ctor<CODE> </CODE>sum_val<CODE> </CODE>;;<BR><CODE>val sum_val : sum_ex1 = Ctor (Ctor (Ctor (Ctor (Ctor ...))))</CODE><BR><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>val_record_1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>field<CODE> </CODE><CODE>=</CODE><CODE> </CODE>val_record_2<CODE> </CODE>}<CODE> </CODE><BR><CODE> </CODE><B>and</B><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>val_record_2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>field<CODE> </CODE><CODE>=</CODE><CODE> </CODE>val_record_1<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val val_record_1 : record_ex1 = {field={field={field={field={field=...}}}}}</CODE><BR><CODE>val val_record_2 : record_ex1 = {field={field={field={field={field=...}}}}}</CODE><BR>

</PRE>
<BR>
<BR>
Arbitrary planar trees can be represented by such a data structure.<BR>
<BR>


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Vertex<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE>list<CODE> </CODE>;;<CODE> </CODE><BR><CODE>type 'a tree = | Vertex of 'a * 'a tree list</CODE><BR># <B>let</B><CODE> </CODE>height_1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val height_1 : int tree = Vertex (0, [])</CODE><BR># <B>let</B><CODE> </CODE>height_2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[</CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>,[]</CODE><TT>)</TT>;<CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>2</CODE><CODE>,[]</CODE><TT>)</TT>;<CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>3</CODE><CODE>,[]</CODE><TT>)</TT><CODE> </CODE><CODE>]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val height_2 : int tree =</CODE><BR><CODE>  Vertex (0, [Vertex (1, []); Vertex (2, []); Vertex (3, [])])</CODE><BR># <B>let</B><CODE> </CODE>height_3<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[</CODE><CODE> </CODE>height_2;<CODE> </CODE>height_1<CODE> </CODE><CODE>]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val height_3 : int tree =</CODE><BR><CODE>  Vertex</CODE><BR><CODE>   (0,</CODE><BR><CODE>    [Vertex (0, [Vertex (...); Vertex (...); Vertex (...)]); Vertex (0, [])])</CODE><BR><BR><CODE>(* same with a record *)</CODE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>tree_rec<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>label<CODE>:</CODE><I>'a</I><CODE> </CODE>;<CODE> </CODE>sons<CODE>:</CODE><I>'a</I><CODE> </CODE>tree_rec<CODE> </CODE>list<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type 'a tree_rec = { label: 'a; sons: 'a tree_rec list }</CODE><BR># <B>let</B><CODE> </CODE>hgt_rec_1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>label<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>sons<CODE>=[]</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val hgt_rec_1 : int tree_rec = {label=0; sons=[]}</CODE><BR># <B>let</B><CODE> </CODE>hgt_rec_2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>label<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>sons<CODE>=[</CODE>hgt_rec_1<CODE>]</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val hgt_rec_2 : int tree_rec = {label=0; sons=[{label=0; sons=[]}]}</CODE><BR>

</PRE>
<BR>
<BR>
We might think that an enumerated type with only one constructor is not useful,
but by default, Objective CAML does not accept recursive type abbreviations.


<PRE>
<CODE> </CODE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE>list<CODE> </CODE>;;<BR><CODE>Characters 7-34:</CODE><BR><CODE>The type abbreviation tree is cyclic</CODE><BR>

</PRE>
<BR>
<BR>
We can define values with such a structure, but they do not have the same type.


<PRE><BR># <B>let</B><CODE> </CODE>tree_1<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val tree_1 : int * 'a list = 0, []</CODE><BR># <B>let</B><CODE> </CODE>tree_2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[</CODE><CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>,[]</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>2</CODE><CODE>,[]</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>3</CODE><CODE>,[]</CODE><TT>)</TT><CODE> </CODE><CODE>]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val tree_2 : int * (int * 'a list) list = 0, [1, []; 2, []; 3, []]</CODE><BR># <B>let</B><CODE> </CODE>tree_3<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,[</CODE><CODE> </CODE>tree_2;<CODE> </CODE>tree_1<CODE> </CODE><CODE>]</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val tree_3 : int * (int * (int * 'a list) list) list =</CODE><BR><CODE>  0, [0, [...; ...; ...]; 0, []]</CODE><BR>

</PRE>
<BR>
<BR>
In the same way, Objective CAML is not able to infer a type for a function whose
argument is a value of this form.


<PRE><BR># <B>let</B><CODE> </CODE>max_list<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.fold_left<CODE> </CODE>max<CODE> </CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>val max_list : int list -&gt; int = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>height<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>_,[]</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vertex<CODE> </CODE><TT>(</TT><CODE>_,</CODE>sons<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>max_list<CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>height<CODE> </CODE>sons<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val height : 'a tree -&gt; int = &lt;fun&gt;</CODE><BR><BR><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>height2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE>_,[]</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><CODE>_,</CODE>sons<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>max_list<CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>height2<CODE> </CODE>sons<TT>)</TT><TT>)</TT><CODE> </CODE>;;<CODE> </CODE><BR><CODE>Characters 95-99:</CODE><BR><CODE>This expression has type 'a list but is here used with type</CODE><BR><CODE>  ('b * 'a list) list</CODE><BR>

</PRE>
<BR>
<BR>
The error message tells us that the function <TT>height2</TT> could be typed,
if we had type equality between <I>'a</I> and <I>'b * 'a list</I>, and
precisely this equality was denied to us in the declaration of the type
abbreviation <I>tree</I>.<BR>
<BR>
However, object typing allows to build values, whose type is cyclic.
Let us consider the following function, and try to guess its type.


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x#copy<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE> </CODE>;;<BR>

</PRE>

The type of <TT>x</TT> is a class with method <TT>copy</TT>. The type of this
method should be the same as that of <TT>x</TT>, since equality is tested
between them. So, if <I>foo</I> is the type of <TT>x</TT>, it has the form:
<I>&lt; copy : foo ; .. &gt;</I>. From what has been said above, the type of this
function is cyclic, and it should be rejected; but it is not:


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x#copy<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val f : (&lt; copy : 'a; .. &gt; as 'a) -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>

Objective CAML does accept this function, and notes the type cyclicity using
<B>as</B>, which identifies <I>'a</I> with a type containing <I>'a</I>.<BR>
<BR>
In fact, the problems are the same, but by default, Objective CAML will not accept
such types unless objects are concerned. The function <TT>height</TT> is
typable if it gives a cyclicity on the type of an object.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>height<CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>a#sons<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>l<CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>max_list<CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>height<CODE> </CODE>l<TT>)</TT><TT>)</TT><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val height : (&lt; sons : 'a list; .. &gt; as 'a) -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora207.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora209.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
